package leetcode.code1314;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int[][] matrixBlockSum(int[][] mat, int k) {
		int m = mat.length;
		int n = mat[0].length;
		int[][] sums = new int[m + 1][n + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
			}
		}
		int[][] ans = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int p = i - k, q = j - k, P = i + k, Q = j + k;
				p = p < 0 ? 0 : p;
				q = q < 0 ? 0 : q;
				P = P >= m ? m : P + 1;
				Q = Q >= n ? n : Q + 1;
				ans[i][j] = sums[P][Q] - sums[P][q] - sums[p][Q] + sums[p][q];
			}
		}
		return ans;
	}

	int m, n;
	// (i,j)
	// (I,J)
	private int f(int[][] sums, int p, int q, int P, int Q) {
		p = p < 0 ? 0 : p;
		q = q < 0 ? 0 : q;
		P = P >= m ? m : P + 1;
		Q = Q >= n ? n : Q + 1;
		return sums[P][Q] - sums[P][q] - sums[p][Q] + sums[p][q];
	}

	private int[][] sums(int[][] mat) {
		int[][] sums = new int[m + 1][n + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
			}
		}
		return sums;
	}

	@Override
	public void debug4() {
		H.compare(4, this.matrixBlockSum(H.str2array1("[[1,2,3],[4,5,6],[7,8,9]]"), 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
